Given a black and white image, represented by an array of $\surd n x \surd n$ binary valued pixels, we wish to cover the black pixels with a minimal set of (possibly overlapping) maximal squares. It was recently shown that obtaining a minimum cover with squares for a polygonal binary image having holes is NP-hard. We derive an optimal parallel algorithm for the minimal square cover problem, which for any desired computation time T in [log n, n] runs on an EREW-PRAM with (n/T) processors. The cornerstone of our algorithm is a novel data structure, the cover graph, which compactly represents the covering relationships between the maximal squares of the image. The size of the cover graph is linear in the number of pixels. This algorithm has applications to problems in VLSI mask generation, incremental update of raster displays, and image compression.
展开▼
机译：给定一个黑白图像，该数组由$ \ surd n x \ surd n $二进制值像素数组表示，我们希望用一组最小的（可能重叠的）最大平方覆盖黑色像素。最近显示，对于具有孔的多边形二进制图像，获得具有正方形的最小覆盖是NP难的。我们推导了用于最小平方覆盖问题的最佳并行算法，该算法对于[log n，n]中任何所需的计算时间T，都在具有（n / T）个处理器的EREW-PRAM上运行。我们算法的基石是一种新颖的数据结构，即覆盖图，它紧凑地表示了图像的最大平方之间的覆盖关系。封面图的大小在像素数上是线性的。该算法可用于解决VLSI掩码生成，光栅显示的增量更新和图像压缩等问题。
展开▼
